package com.xiaoyu.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: DS_and_A
 * @description:
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * @author: YuWenYi
 * @create: 2021-05-04 10:07
 **/
/*
    有缺陷的思路,{-1,6},{6,8},{8,10},{15,18}这种就不行
*   for (int i = 0; i < intervals.length; i++) {
            int j = i + 1 == intervals.length ? i : i + 1;
            if (intervals[i][1] >= intervals[j][0]){
                res[i][0] = intervals[i][0];  //由于排序,那么左边界的值一定是后面的大于前面的!
                res[i][1] = Math.max(intervals[i][1], intervals[j][1]); //但是右边界无法确定谁大,需要进行比较再赋值
                resList.add(res[i]);  //然后把res的结果,加到集合中
                i++;  //由于下一个区间已经被使用过,所以i++跳过它
            }else {
                res[i][0] = intervals[i][0];
                res[i][1] = intervals[i][1];
                resList.add(res[i]);
            }
        }
*
* */
public class MergeRange {

    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][2];
        //先对数组进行排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        //使用一个集合来保存数据
        ArrayList<int[]> resList = new ArrayList<>();
        int i = 0;
        while (i < intervals.length){
            int left = intervals[i][0];  //默认是以当前数组的左右值为边界
            int right = intervals[i][1];
            while (i < intervals.length - 1 && intervals[i+1][0] <= right){  //如果发现需要合并,则去合并下一个区间
                i++;  //由于下一个区间已经被使用过,所以i++跳过它
                right = Math.max(intervals[i][1], right); //比较当前边界和下一个边界谁更大
            }
            resList.add(new int[]{left,right});
            i++;
        }
        return resList.toArray(new int[0][]);  //将集合转换成一个二维数组
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{-1,6},{6,7},{8,10},{15,18}};

        int[][] mergeRange = merge(intervals);

        for (int[] m : mergeRange) {
            System.out.println(Arrays.toString(m));
        }
    }
}
